This invention relates to high-density printed codes and, in particular, to high-density printed codes that have improved damage-tolerance. In addition, the invention concerns high-density printed codes capable of storing multiple biometrics and text for positive identity identification. Further, the invention concerns off-line positive identity identification apparatus capable of operating in combination with high-density printed codes storing multiple biometrics.
Numerous technologies have been developed over the past two decades that are capable of storing significant amounts data (on the order of a kilobyte or more) in a small, compact space (a few square inches or less). Such technologies include so-called xe2x80x9csmart cardsxe2x80x9d; CD-ROM-based optical storage media; magnetic stripe cards; and two-dimensional high-capacity printed bar codes and matrix codes. Depending on the overall information capacity of the medium, each of these technologies may be suitable for storing biometric information for use in positive identity verification applications. Each of these technologies has its advantages and disadvantages in this specific application and other applications.
One of the primary advantages of two-dimensional high-capacity printed bar codes and matrix codes results from the fact that they can be created using conventional printing techniques (including laser printers). One application among many for these codes is in positive identity verification programs where such codes are used to identify human beings. Due to the often enormous number of identification documents that may be created in positive identity verification programs, the fact that two-dimensional printed codes can be formed by conventional printing techniques provides a significant cost advantage over xe2x80x9csmart cards,xe2x80x9d CD-ROM-based optical storage media; and magnetic stripe cards. Further, error-corrected two-dimensional printed codes are far more robust than smart cards with respect to the ability to tolerate electromagnetic fields, radiation and mechanical stress and CD-ROM-based optical storage media with respect to the ability to withstand scuffing and scratching. xe2x80x9cSmart cardsxe2x80x9d incorporate circuitry and chips that may be damaged should the card be flexed, limiting the suitability of the card for low-cost applications.
Within the art of printed codes, over the past decade, numerous two-dimensional printed paper-based codes have been introduced. These codes represent a substantial improvement over prior one-dimensional bar codes in a number of areas. Most importantly, these codes are capable of storing hundreds of bytes of information, approaching a kilobyte, in a few square inches. In contrast, prior one-dimensional bar codes were capable of storing only a few characters, on the order of ten or twelve, in roughly the same space.
Such codes also exhibit improved error detection and correction capability. For example, one such code, PDF417, disclosed in U.S. Pat. No. 5,304,786, employs the Reed-Solomon error correcting method to improve the damage-tolerance of the code.
Using the Reed-Solomon error correcting method, additional codewords are appended to the end of the data codewords appearing in the PDF417 symbol. If a substantial contiguous portion of the code were to be destroyed or otherwise rendered unreadable (a likely possibility due to the often rugged conditions these codes encounter, e.g., on the outside of a shipping parcel, or on a part on an assembly line), the data represented in the data codewords can still be recovered by reading the Reed-Solomon error correction codewords included in the symbol.
One drawback of PDF417 is the fact that it employs an (n, k) bar code encoding methodology based on 929 codewords. As a result, each PDF417 codeword has a data capacity of 9.25 bits. Given the length of the codeword (17 bits), this results in a substantial overhead (redundant portion of the code). In addition, PDF417 is capable of storing only about 1500 bytes of information with minimal levels of error correction, and much less in the case with acceptable levels of error correction.
Another code is the data strip code disclosed and claimed in U.S. Pat. No. 4,782,221. The data strip code disclosed and claimed in U.S. Pat. No. 4,782,221 is capable of storing up to a kilobyte or more of information in a small space but is vulnerable to data loss in the case of large area destruction due to the relatively limited error correction capability of the code.
Other two-dimensional printed codes include matrix codes, e.g., Datamatrix, or the UPS Maxicode, which have been used in small parts identification and package sortation. These codes have features that facilitate discrimination of the code from a background that is particularly useful when the code is being scanned by a reading device placed above a conveyer belt on which the part or parcel is moving. These codes, while particularly useful in such applications, have not been found to be suitable where large amounts of information are sought to be encoded in a relatively small amount of space.
Overcoming the limitations of these prior printed codes is particularly important because a major application for such codes is off-line positive identity verification. In such applications, biometrics that provide a positive identity verification capability are encoded in the two-dimensional code. Such codes, when operating with apparatus capable of decoding the code, permit positive identity verification to occur independent of a central database storing such identity verification information. This lends a great deal of flexibility in instances where temporary installations are used by governments, e.g., in voting; voting might occur in an installation not having a fixed identity verification apparatus or connection to a central identity database. Having a printed code encoding identity information permits positive identity verification to occur without a permanent positive identity verification apparatus in place.
In order to function effectively in such off-line positive identity verification applications, two-dimensional printed codes must be capable of storing biometric information used in positive identity verification. In addition, the codes storing biometric information must be tailored to fit on standard-sized identity verification papers like, e.g., conventionally-sized ISO cards or passports. These standards are set forth in the International Civil Aviation Organization document entitled Machine Readable Travel Documents 9303 Parts 1-4. Document 9303 Parts 1-4 identifies a number of standard-sized travel documents including machine readable official travel document 1 (MROTD1) card (the ubiquitous ISO CR-80 credit-card sized card which is 2.125xc3x973.375 inches and in the MRTOD1 application allocates 0.98xc3x973.13 inches to a two-dimensional printed code); the oversized identification card (designated MROTD2 and which allocates 0.72xc3x972.52 inches for a two-dimensional printed code); and a conventional passport page (which allocates 0.72xc3x973.14 inches for a two-dimensional printed code.
These standards illustrate that even with the advent of machine-readable codes, standards organizations are still unwilling to dedicate all or most of a document to a machine-readable code and instead specify standards that leave large areas in which to print human-readable information. As a result, real estate on such documents is precious and most be used efficiently, indicating the desirability of even higher density two-dimensional printed codes.
Due to the requirements of known compression techniques for compressing files storing biometric information, known two-dimensional codes have relatively limited capability for providing highly-accurate positive identity verification where such identification is dependent on storing multiple biometrics. For example, known data compression techniques create files that are on the order of 500-750 bytes per fingerprint template (uncompressed) and 900-1100 bytes (compressed) for a photographic image of a person. Thus, a government agency or private company interested in establishing a positive identity verification program based on encoding three fingerprint templates; a photograph; and text would be seeking to store on the order of 2800 bytes of information in a known two-dimensional code. There are no known two-dimensional printed codes capable of storing that much information in a single code symbol with a level of error correction that would provide robust, damage-tolerant performance.
As a result, such an application would require on-line capability, i.e., some biometric information would have to be stored in a central database in order to achieve highly accurate positive identification. This would limit the flexibility of the system, because personnel interested in positively identifying individuals would require a dedicated connection to the database for as long as they were performing identity verification.
In addition, known off-line verification apparatus capable of operating with desired two-dimensional, high-density damage-tolerant printed codes are relatively bulky and depend on separate units for performing various operations necessary to positively verify identity, e.g., fingerprint scanning; fingerprint minutiae extraction; comparison of fingerprint minutiae with fingerprint record stored in printed code; and comparison of photographic images with stored images. These operations may require multiple, stand-alone units, thereby limiting the flexibility of the system, and they may effectively mandate fixed identity verification stations even in off-line positive identity verification applications.
Thus, it is desired to have a two-dimensional printed code having improved information capacity.
It is also desired to have a two-dimensional printed code having improved damage tolerance.
It is further desired to have a two-dimensional, high-density, damage-tolerant printed code capable of storing multiple, high-quality biometrics.
It is also desired to have a conventionally-sized ISO card or other conventional identification paper bearing a two-dimensional, high-density, damage-tolerant printed code storing multiple, high-quality biometrics.
It is further desired to have a conventionally-sized ISO card or other conventional identification papers bearing a two-dimensional, high-density, damage-tolerant printed code storing multiple, high-quality biometrics that may be used in off line positive identity verification applications.
It is also desired to have a fully-integrated, compact off-line positive identity verification apparatus capable of operating with conventionally-sized identity verification papers bearing two-dimensional printed codes encoding multiple, high-quality biometrics.
Accordingly, it is an object of the present invention to provide a two-dimensional printed code having improved information capacity.
It is another object of the present invention to provide a two-dimensional printed code having improved damage tolerance.
It is a further object of the present invention to provide a two-dimensional, high-density, damage-tolerant printed code capable of storing multiple, high-quality biometrics.
It is yet another object of the present invention to provide conventionally-sized ISO card or other identity verification papers capable of bearing a two-dimensional, high-density damage tolerant printed code encoding multiple, high-quality biometrics for use in off-line, positive identity verification applications.
It is a yet further object of the present invention to provide a fully-integrated, compact, hand-held, off-line positive identity verification apparatus capable of providing identity verification with a high degree of accuracy by recovering biometric information encoded in a two-dimensional, high-density, damage-tolerant printed code.
The foregoing objects are accomplished by the present invention of a two-dimensional, high-density, damage tolerant printed code suitable for encoding multiple biometrics and text for positive off-line identity verification. In a preferred embodiment, such a code comprises a horizontal header section; a vertical header section; a start pattern; a left row address pattern; an encoded user data portion; a right row address pattern; and a stop pattern. The horizontal header section encodes the number of bit areas in a transverse row of the encoded information portion; and the vertical header section encodes the vertical height of each bit area. The start and stop patterns of the code demarcate the lateral extent of the code (i.e., the beginning and end) from the adjacent quiet zone. Information is encoded into the encoded information portion in bit areas that may be printed or blank. The encoded user data is printed sequentially in the encoded user data portion from the top of the encoded information along each transverse row of bit areas to the next row of bit areas until the end of the encoded information portion.
In the preferred embodiment, prior to encoding, the user information to be encoded in the information portion is divided into a number of packets that represent sequential subunits of information. A subunit of each packet (e.g., a byte comprising the most significant bits of each packet) is selected and then combined into an error correction packet for error correction purposes. A conventional error correction algorithm is then applied to this first error correction packet for error correction purposes. A number of error correction bits are then created, and these are appended to the end of the user information portion. The process is then repeated by selecting the next most significant bits from each packet and combining them into an error correction packet for error correction purposes. The error correction algorithm is then applied to this second error correction packet to create a number of error correction bits. These error correction bits are then appended to the user information and first collection of error correction bits. The process is repeated until all the information in each packet has been error corrected. The information is then formatted into a file that, when printed, will constitute a two-dimensional, high-density, damage-tolerant, printed code.
In another embodiment of the present invention the user information to be encoded in the two-dimensional printed code is arrayed in computer memory in the row-column sequence in which it is to be printed in the two-dimensional, high-density, damage-tolerant printed code. The row-column organized information is then divided into a number of two-dimensional packets of (n, m) dimension that represent contiguous bits to be printed in the two-dimensional printed code. A subunit of bits is selected from each of said two-dimensional packets of (n, m) dimension and combined into a first error correction packet for error correction purposes. An error correction algorithm is then applied to the first error correction packet. The error bits thus created in this first step are next formed into a two-dimensional collection of bits to be printed contiguously after the user data. The process is continued until error correction information is created for all user information.
In a further embodiment of the present invention, the control data indicating the length of the file encoded in the two-dimensional printed code and the level and manner of error correction are separately error corrected to create a number of error correction bits for use in case of catastrophic damage to that portion of the code encoding the control data. In fixed length and fixed error correction format codes, this information is interspersed at known locations throughout the code to provide robust damage tolerance. In variable length and error correction codes, the header can store the location of the control data error correction bits by encoding a number corresponding to one from a number of options. This indicates where the reader should look for the error correction bits corresponding to the control data in the case of catastrophic damage to the control data portion of the code.
Two-dimensional, high-density, damage-tolerant printed codes made in accordance with the foregoing embodiments are capable of encoding 2800 bytes of information (sufficient for multiple biometrics (fingerpints and image) and text) with a robust level of error correction resulting in an overall message length of 3400 bytes. The information would be printed in a code having an encoded user data portion of 0.84 inches by 2.87 inches (the minimum feature having a size of 0.0066xc3x970.010 inches). Such a printed code would easily fit on a portion of one side of a conventional 2.125xc3x973.375 inch card, leaving substantial space for human readable information on the remaining portion of the card.
In yet another embodiment of the present invention, a two-dimensional, high-density, damage tolerant printed code encoding multiple biometric information and text is imprinted on conventionally-sized ISO cards or other identification documents (e.g., passports) for use in off-line positive identity verification applications.
A yet further embodiment of the present invention comprises a fully-integrated, compact, hand-held (the apparatus can also be counter-mounted or wall-mounted), off-line positive identity verification apparatus having scanning means which may include a scanned one-dimensional charge-coupled device (1D CCD); a CMOS contact image sensor or other 1D sensors; or a two-dimensional charge-coupled device (2D CCD) for recovering biometric information stored in a two-dimensional, high-density, damage tolerant printed codes; real-time biometric capture capabilities (e.g., for capturing fingerprints); a microprocessor and associated programming for comparing real time biometric information captured from an individual whose identity is sought to be verified with biometric information recovered from a two-dimensional printed code; and indication apparatus to indicate whether as a result of the biometric comparison process the individual has been identified as authentic or an impostor.
A yet further embodiment of the present invention comprises the combination of a two-dimensional, high-density, damage-tolerant printed code and a fully-integrated, compact, hand-held (the apparatus can also be counter-mounted or wall-mounted) off-line positive identity verification apparatus. The fully-integrated, compact, hand-held off-line positive identity verification apparatus has a scanner for recovering biometric information from a two-dimensional, high-density, damage-tolerant printed code, and real-time biometric capture capability for capturing biometric information from the person whose identity is sought to be verified. The positive identity verification apparatus then compares the biometric information to determine whether the individual is authentic or an impostor.
From the foregoing description, a number of advantages of the present invention become apparent. First, the invention provides a two-dimensional, damage-tolerant, printed code with both improved total information capacity and improved high information density performance. This is accomplished through a code format that provides both a high information capacity and a robust level of error correction in a small space. Second, the invention provides a two-dimensional, high-density, damage-tolerant printed code capable of storing multiple biometrics that makes possible a highly-accurate off-line positive identity verification by comparing biometrics captured in real-time from an individual whose identity is sought to be verified with biometrics recovered from the printed code. Third, the invention provides a fully-integrated, compact, hand-held off-line positive identity verification apparatus that greatly increases the flexibility of positive identity verification operations by making both the identity verification information (stored in a small card) and identity verification apparatus (fully-integrated and hand-held) highly mobile. No longer are governments or private businesses interested in establishing positive identity verification programs relegated to storing such information in a central data base generally accessible only from fixed-site, dedicated positive identity verification installations.